package binarytree

// 思路：
// 1. 递归地计算每个节点的左子树和右子树的高度。
// 2. 如果某个节点的左右子树高度差大于1，则该树不平衡。
// 3. 如果所有节点都满足平衡条件，则该树是平衡的。

func IsBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}

	leftHeight := height(root.Left)
	rightHeight := height(root.Right)

	if abs(leftHeight-rightHeight) > 1 {
		return false
	}

	return IsBalanced(root.Left) && IsBalanced(root.Right)
}
func height(node *TreeNode) int {
	if node == nil {
		return 0
	}
	leftHeight := height(node.Left)
	rightHeight := height(node.Right)

	if leftHeight > rightHeight {
		return leftHeight + 1
	}
	return rightHeight + 1
}
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

// 优化一下
// 实际上在计算高度的过程中就可以判断是否平衡
// 这样就不需要每次都递归计算高度了，减少了时间复杂度
func IsBalancedOptimized(root *TreeNode) bool {
	if root == nil {
		return true
	}

	_, balanced := checkBalance(root)
	return balanced
}

// checkBalance 返回节点的高度和是否平衡
func checkBalance(node *TreeNode) (height int, balanced bool) {
	if node == nil {
		return 0, true
	}

	leftHeight, leftBalanced := checkBalance(node.Left)
	rightHeight, rightBalanced := checkBalance(node.Right)

	// 高度还是比较好计算的，就是左右子树的更大高度加1即可
	height = max(leftHeight, rightHeight) + 1
	// 是否平衡取决于左右子树是否平衡以及左右子树高度差是否小于等于1，只有全都具备，才是平衡的
	balanced = leftBalanced && rightBalanced && abs(leftHeight-rightHeight) <= 1

	return height, balanced
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
